
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1722. -- [Usaco2006 Mar] Milk Team Select -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1722: [Usaco2006 Mar] Milk Team Select</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>85&nbsp;&nbsp;<span class=green>Solved: </span>47<br>[<a href='submitpage.php?id=1722'>Submit</a>][<a href='problemstatus.php?id=1722'>Status</a>][<a href='bbs.php?id=1722'>Discuss</a>]</center><h2>Description</h2><div class=content>Farmer John's N (1 <= N <= 500) cows are trying to select the
milking team for the world-famous Multistate Milking Match-up (MMM)
competition. As you probably know, any team that produces at least
X (1 <= X <= 1,000,000) gallons of milk is a winner.

Each cow has the potential of contributing between -10,000 and
10,000 gallons of milk. (Sadly, some cows have a tendency to knock
over jugs containing milk produced by other cows.)

The MMM prides itself on promoting family values. FJ's cows have
no doubt that they can produce X gallons of milk and win the contest,
but to support the contest's spirit, they want to send a team with
as many parent-child relationships as possible (while still producing
at least X gallons of milk). Not surprisingly, all the cows on FJ's
farm are female.

Given the family tree of FJ's cows and the amount of milk that each
would contribute, compute the maximum number of parent-child
relationships that can exist in a winning team. Note that a set of
cows with a grandmother-mother-daughter combination has two
parent-child relationships (grandmother-mother, mother-daughter).
</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers, N and X.

* Lines 2..N+1: Line i+1 contains two space-separated integers
        describing cow i. The first integer is the number of gallons
        of milk cow i would contribute. The second integer (range
        1..N) is the index of the cow's mother. If the cow's mother is
        unknown, the second number is 0. The family information has no
        cycles: no cow is her own mother, grandmother, etc.


N头牛,要选出一些来使其产奶量大于等于X.
问最多可选出几对父子关系出来.
如果选出来的集合中有爷爷点,父亲点,儿子点，则交有两对父子关系.</div><h2>Output</h2><div class=content>* Line 1: The maximum number of parent-child relationships possible on
        a winning team. Print -1 if no team can win.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 8<br />
-1 0   //第一个数字代表这头奶的产量,第二个数字代表其父亲点是哪一个.<br />
3 1<br />
5 1<br />
-3 3<br />
2 0<br />
<br />
INPUT DETAILS:<br />
<br />
There are 5 cows. Cow 1 can produce -1 gallons and has two daughters, cow<br />
2 and 3, who can produce 3 and 5 gallons, respectively. Cow 3 has a<br />
daughter (cow 4) who can produce -3 gallons. Then there's cow 5, who can<br />
produce 2 gallons.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2<br />
<br />
OUTPUT DETAILS:<br />
<br />
The best team consists of cows 1, 2, 3, and 5. Together they produce<br />
(-1)+3+5+2 = 9 >= 8 gallons and have 2 parent-child relationships<br />
(1--2 and 1--3). Note that a team with cows 2, 3, and 5 would be<br />
able to produce more milk (10 gallons), but would have fewer<br />
parent-child relationships (0).</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1722'>Submit</a>][<a href='problemstatus.php?id=1722'>Status</a>][<a href='bbs.php?id=1722'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
